--[[
Provides support for object-oriented programming with full dynamic multiple inheritance using C3
linearization to compute the method resolution order of each class.
--]]
module(..., package.seeall)

-- Forward declaractions for C3-related and auxiliary functions
local C3_linearization
local C3_build_class_lists
local C3_merge_class_lists
local C3_is_linearizable
local C3_purge_class

local copy_table
local index_of

----------------------------------------------------------------------------------------------------
-- Set up the base class for all classes
----------------------------------------------------------------------------------------------------
class = {}
setmetatable(class, class)
class.__name = "class"
class.__bases = {}
class.__mro = {class}
class.__metatable = class  -- disables setmetatable() for all class tables (including class itself)

----------------------------------------------------------------------------------------------------
-- Constructors of class tables and class instances, and inheritance
----------------------------------------------------------------------------------------------------
function class.new(cls, ...)
    --[[ Create a new class instance. Note that this function will call __new() on the class to
    provide a pre-initialized table (otherwise a new empty table will be used). Then, the class'
    __init() method will be called with the object itself as the first argument. Note that the
    object's metatable is already set when __init() is called. ]]
    
    -- create the object by calling the class' __new() method or copying __new if 
    -- it is a table. if __new is of any other type then an empty table is created
    local obj
    local new = cls.__new
    if type(new) == "table" then
        obj = copy_table(new)
    elseif type(new) == "function" then
        obj = new(cls, ...)
    else
        obj = {}
    end
    -- if the object returned by __new() already has a metatable, we copy the contents of all 
    -- ancestor classes (in mro reverse order) onto the object itself. Note that inheritance is 
    -- not dynamic anymore in this case, since the object got a snapshot of the class and all its 
    -- ancestors copied into it. Future changes to any class will not affect the object.
    -- If the object does not have a metatable set, we set the object's metatable to be 'cls', 
    -- thereby providing it with fully dynamic inheritance, i.e. future changes to its class or 
    -- any ancestor class will be reflected in the object.
    if getmetatable(obj) ~= nil then
        print "warning: class.new() - dynamic inheritance not possible for object."
        local original_obj = copy_table(obj)
        local mro = cls.__mro
        for i = #mro, 1, -1 do
            copy_table(mro[i], obj)
        end
        copy_table(original_obj, obj)
    else
        setmetatable(obj, cls)
    end
    -- finally, if obj.__init() is a function, we call it on the object with the same arguments 
    -- that were passed to new(). If it is a table, it is copied onto obj, and nothing is done if 
    -- __init is of any other type (note that this includes nil).
    local init = cls.__init
    if type(init) == "table" then
        copy_table(init, obj)
    elseif type(init) == "function" then
        init(obj, ...)
    end
    return obj
end

function class.__call(cls, ...)
    --[[ Calling a class table 'cls' is the same as calling its new() method, i.e. 'cls:new()'. ]]
    return cls:new(...)
end

function class.__new(metacls, name, ...)
    --[[ Create a new class table with the specified list of superclasses. ]]
    local bases = {...}
    local found = {}
    for _, base in ipairs(bases) do
        if found[base] then
            error("duplicate base class found", 2)
        end
        found[base] = true
    end
    local cls = {__name=name, __bases=bases}
    local mro, error_message = C3_linearization(cls)
    if mro == nil then
        error(error_message, 2)
    end
    cls.__mro = mro          -- method resolution order (lookup sequence for missing fields)
    cls.__metatable = cls    -- disables setmetatable() for instances of this class
    cls.__index = cls        -- provide inheritance to instances of this class
    cls.new = metacls.new    -- provide a constructor to the newly created class
    return cls
end

function class.__tostring(cls)
    local metacls = getmetatable(cls)
    local bases = ""
    if #cls.__bases > 0 then
        bases = {}
        for _, base in ipairs(cls.__bases) do
            table.insert(bases, base.__name)
        end
        bases = "(" .. table.concat(bases, ", ") .. ")"
    end
    return string.format("<%s %s%s>", metacls.__name, cls.__name, bases)
end

function class.__index(cls, key)
    --[[ Implements inheritance of data attributes and functions. Lookup is done by traversing the
    mro list until some ancestor class provides the requested field. If the requested field is not 
    found in any of the class' ancestors, nil is returned (which is the standard behavior of Lua 
    tables for missing fields). ]]
    local mro = cls.__mro
    for i = 2, #mro do                     -- we can skip the class itself, since the __index()
        local value = rawget(mro[i], key)  -- metamethod wouldn't even be called if the class
        if value ~= nil then               -- had the requested field
            return value
        end
    end
    return nil
end

----------------------------------------------------------------------------------------------------
-- Functions for checking instances and subclasses
----------------------------------------------------------------------------------------------------
function issubclass(A, B)
    --[[ issubclass() function similar to Python's function with the same name. This works by
    traversing A's mro and checking for the presence of B. Therefore, issubclass(A, A) returns
    true since a class is always the first element of its own mro. ]]
    for _, cls in ipairs(A.__mro) do
        if cls == B then return true end
    end
    return false
end

function isinstance(obj, cls)
    --[[ isinstance() function works like Python's function with the same name. ]]
    if cls == nil then
        error("missing class argument in isinstance()", 2)
    end
    local obj_cls = getmetatable(obj)
    return obj_cls ~= nil and issubclass(obj_cls, cls)
end

function members(obj)
    --[[ Returns a list with all attributes available to a given object, either directly or 
    through inheritance. ]]
    local cls
    if isinstance(obj, class) then
        cls = obj
        obj = nil
    else
        cls = getmetatable(obj)
    end
    local members = {}
    local mro = cls.__mro
    for i = #mro, 1, -1 do
        copy_table(mro[i], members)
    end
    if obj ~= nil then
        copy_table(obj, members)
    end
    return members
end

----------------------------------------------------------------------------------------------------
-- Make symbols available in the global environment
----------------------------------------------------------------------------------------------------
_G.class = class
_G.issubclass = issubclass
_G.isinstance = isinstance
_G.members = members

----------------------------------------------------------------------------------------------------
-- C3 method resolution order functions
----------------------------------------------------------------------------------------------------
function C3_linearization(cls)
    --[[ Compute a method resolution order (or field lookup sequence) for this class. We use the
    C3 linearization algorithm as explained in http://www.python.org/download/releases/2.3/mro/
    ]]
    local class_lists = C3_build_class_lists(cls)
    return C3_merge_class_lists(cls, class_lists)
end

function C3_build_class_lists(cls)
    --[[ First we create a list of lists of classes, containing the MROs  of all superclasses
    plus our list of superclasses at the end. ]]
    local class_lists = {}
    for _, base in ipairs(cls.__bases) do
        table.insert(class_lists, copy_table(base.__mro))
    end
    if #cls.__bases > 0 then
        table.insert(class_lists, copy_table(cls.__bases))
    end
    return class_lists
end

function C3_merge_class_lists(cls, class_lists)
    --[[ This is where the magic happens :) In this function we actually build the MRO list. ]]
    local mro = {cls}
    while #class_lists > 0 do
        -- search for an eligible head
        local eligible = nil
        for i = 1, #class_lists do
            local head = class_lists[i][1]
            if C3_is_linearizable(head, class_lists) then
                eligible = head
                break
            end
        end
        -- insert the head in the MRO and remove it from all class lists
        if eligible ~= nil then
            C3_purge_class(eligible, class_lists)
            table.insert(mro, eligible)
        -- or return an error message if no eligible head could be found
        else
            return nil, "ambiguous class hierarchy (unable to compute MRO)"
        end
    end
    return mro
end

function C3_is_linearizable(cls, class_lists)
    --[[ Verify if the given class can be legally added to the MRO. For a class to be eligible for
    linearization, the argument class can only appear as the head (the first element) of any class
    list, or not appear at all in the list. If it is found in the tail (elements 2 and beyond) of
    any class list, then it is not eligible for insertion into the MRO. ]]
    for _, class_list in ipairs(class_lists) do
        local index = index_of(class_list, cls)
        if index ~= nil and index > 1 then
            return false
        end
    end
    return true
end

function C3_purge_class(cls, class_lists)
    --[[ Remove all occurrences of a class for all class lists (note that the class can only
    appear as the head of any list), getting rid of any class lists that would become empty from
    eliminating the class. ]]
    for i = #class_lists, 1, -1 do
        local class_list = class_lists[i]
        if class_list[1] == cls then
            if #class_list == 1 then
                table.remove(class_lists, i)  -- remove class list from "master" list
            else
                table.remove(class_list, 1)   -- remove head of class list
            end
        end
    end
end

----------------------------------------------------------------------------------------------------
-- Auxiliary functions
----------------------------------------------------------------------------------------------------
function copy_table(t1, t2)
    --[[ Create a *shallow* copy of the argument table 't1'. If a second table 't2' is supplied,
    the contents of 't1' are copied into 't2'. ]]
    t2 = t2 or {}
    for k, v in pairs(t1) do
        t2[k] = v
    end
    return t2
end

function index_of(t, x, lo, hi)
    --[[ Return the index or value 'x' in table 't'. Searched indices may be limited by passing
    the 'lo' and 'hi' arguments. ]]
    lo = lo or 1
    hi = hi or #t
    for i = lo, hi do
        if t[i] == x then return i end
    end
    return nil
end

----------------------------------------------------------------------------------------------------
-- Test code (examples taken from http://www.python.org/download/releases/2.3/mro/)
----------------------------------------------------------------------------------------------------
function test()
    local klass
    local show_bases
    local show_mro
    local print = io.write
    local printf = function(...) io.write(string.format(...)) end
    
    klass = class("klass", class)
    klass.__call = class.__call
    klass.__index = class.__index
    
    function klass:__new(name, ...)
        assert(issubclass(self, klass))
        local cls = class.__new(self, name, ...)
        cls.name = name
        cls[name] = name
        show_bases(cls, false)
        show_mro(cls, true)
        assert(cls.__index == cls)
        return cls
    end
    
    function show_bases(cls, nl)
        printf("Bases(%s) = [", cls.name)
        for _, base in ipairs(cls.__bases) do print(" ", base.name) end
        print(" ]. ")
        if nl then print("\n") end
    end

    function show_mro(cls, nl)
        printf("MRO(%s) = [", cls.name)
        for _, ancestor in ipairs(cls.__mro) do print(" ", ancestor.name) end
        print(" ]. ")
        if nl then print("\n") end
    end
    
    local O = klass("O")
    function O:__init(cls)
        cls = cls or getmetatable(self)
        print(cls.name, " ")
        for _, base in pairs(cls.__bases) do
            self:__init(base)
        end
    end
    
    local function test1()
        print("\nTest #1\n")
        local F = klass("F", O)
        local E = klass("E", O)
        local D = klass("D", O)
        local C = klass("C", D, F)
        local B = klass("B", D, E)
        local A = klass("A", B, C)
        local a = A()
        print(a.A, a.B, a.C, a.D, a.E, a.F, a.O, "\n")
        for k, v in pairs(a) do printf("%s = %s\n", k, v) end
    end
    
    local function test2()
        print("\nTest #2\n")
        local A = klass("A", O)
        local B = klass("B", O)
        local C = klass("C", O)
        local D = klass("D", O)
        local E = klass("E", O)
        local K1 = klass("K1", A, B, C)
        local K2 = klass("K2", D, B, E)
        local K3 = klass("K3", D, A)
        local Z = klass("Z", K1, K2, K3)
        local z = Z()
        print(z.O, z.A, z.B, z.C, z.D, z.E, z.K1, z.K2, z.K3, z.Z, "\n")
        for k, v in pairs(z) do printf("%s = %s\n", k, v) end
    end
    
    test1()
    test2()
end

